package code1_100.code20_30;

/**
 * 实现 strStr() 函数。
 *
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 *
 * 输入: haystack = "hello", needle = "ll"
 * 输出: 2
 * 输入: haystack = "aaaaa", needle = "bba"
 * 输出: -1
 *
 * "mississippi"  期望输出：4
 * "issip"
 *
 * "mississippi"  期望输出：-1
 * "issipi"
 *
 */
public class _28strStr {

    public static void main(String[] args) {
        System.out.println(strStr("hello","ll"));
    }

    /**
     * 兜兜转转还是发现源码效率最高
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
     * 内存消耗：36.9 MB, 在所有 Java 提交中击败了88.34% 的用户
     *
     * 可深入观察一下
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr(String haystack,String needle){
        return haystack.indexOf(needle);
    }


    /**
     * KMP算法实现：效果不是太理想
     * 执行用时：2 ms, 在所有 Java 提交中击败了53.44% 的用户
     * 内存消耗：38.4 MB, 在所有 Java 提交中击败了34.79% 的用户
     *
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr2(String haystack, String needle) {
        if (needle == null || needle.length() == 0)
            return 0;
        if (haystack == null || haystack.length() == 0 || needle.length() > haystack.length())
            return -1;

        char[] string = haystack.toCharArray(), pattern = needle.toCharArray();
        int[] next = new int[pattern.length];
        next[0] = -1;
        for (int i = 1, k = -1; i < next.length;) {
            if (k == -1)
                k = next[i] = pattern[0] == pattern[i++] ? 0 : -1;
            else
                k = pattern[i] == pattern[k + 1] ? next[i++] = k + 1 : next[k];
        }

        for (int s = 0, p = 0; s < string.length; s++) {
            if (pattern[p] != string[s] && p != 0) {
                p = next[p - 1] + 1;
                s--;
            } else if (pattern[p] == string[s])
                if (++p == pattern.length)
                    return s - p + 1;
        }
        return -1;
    }

    /**
     * 最低次的二重循环暴力解法：
     * 执行用时：6 ms, 在所有 Java 提交中击败了17.76% 的用户
     * 内存消耗：37.2 MB, 在所有 Java 提交中击败了54.86% 的用户
     *
     * 相对应还有一种暴力的方法，切割字符串，每一次进行切割然后进行equal比较
     * 执行用时：1 ms, 在所有 Java 提交中击败了71.45% 的用户
     * 内存消耗：38.8 MB, 在所有 Java 提交中击败了6.27% 的用户 ，空间占用和字符匹配不可同日而语
     *
     * 优化算法：KMP，保存前面的部分对比信息，但要维护一张表，消耗空间
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr1(String haystack, String needle) {
        //前面的预处理数据
        if(needle==null||needle.length()==0){
            return 0;
        }
        if(haystack==null){
            return -1;
        }
        if(haystack.length()==0&&needle.length()==0){
            return 0;
        }
        //用来标志needle已经匹配的位置
        int label = 0;
        //先使用暴力算法解决一次，双重循环
        for (int i = 0; i < haystack.length(); i++) {
            for (int j = 0; j < needle.length(); j++) {
                //如果后面位数不足以对比，直接返回-1
                if(i+needle.length()>haystack.length()&&label==0){
                        return -1;
                }
                //进行字符的对比
                if (haystack.charAt(i + j) == needle.charAt(j)) {
                    label++;
                }else {
                    label = 0;
                    break;
                }
                //如果对比次数位needle的长度时，表示对比完成
                if (label == needle.length()) {
                    return i;
                }
            }
        }
        return -1;
    }

}
